package someTestExcemple.huaweiOd.unionFindSet;

//华为OD机试 - 计算快递主站点 - 并查集（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/142700111
import java.util.*;
public class ExpressDelivery {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //快递站数量
        int n = sc.nextInt();
        //各站点间连通情况
        int[][] connected = new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                connected[i][j] = sc.nextInt();
            }
        }
        sc.close();
        //1.对每个站点进行def 找到各自能访问的站点，访问过的设置为ture,最后看掉了几次def
/*        boolean[] visited = new boolean[n];
        int count =0;
        for(int i=0;i<n;i++) {
            if(!visited[i]) {
                def(connected,visited,i,n);
                count++;
            }
        }
        System.out.println(count);*/
        //2.并查集合
        //初始化父节点
        int[] parent = new int[n];
        int[] height = new int[n];
        for(int i=0;i<n;i++) {
            parent[i] =i; //每个几点最初都指向自己
            height[i]=-1;
        }
        //遍历各节点，进行节点间合并
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(connected[i][j] == 1) {
                    //可以连通 合并成一个集合
                    union(i,j,parent,height);
                }
            }
        }
        int count =0;
        //找有几个根节点就有几颗树
        for(int i=0;i<n;i++) {
            if(parent[i] == i) {
                count++;
            }
        }
        System.out.println(count);
    }

    public static void def(int[][] connected,boolean[] visited,int i,int n) {
        visited[i] =true;
        for(int t=0;t<n;t++) {
            if(connected[i][t] == 1 && !visited[t]) {
                def(connected,visited,t,n);
            }
        }
    }

    public static void union(int i,int j,int[] parent,int[] height) {
        int parentI = find(i,parent);
        int parentJ =find(j,parent);
        if(parentI != parentJ) {
            if(height[i] < height[j]) {
                parent[i] = parentJ;
            } else if(height[i] > height[j]) {
                parent[j] = parentI;
            } else {
                //两数高度相等
                parent[j] = parentI;
                height[i] +=1;
            }
        }
    }

    public static int find(int i,int[] parent) {
        if(parent[i] != i) {
            parent[i] = find(parent[i],parent);
        }
        return parent[i];
    }

}
